#include <iostream>
#include <vector>

using namespace std;
// 98. 验证二叉搜索树
// 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
// https://leetcode.cn/problems/validate-binary-search-tree/
// 思路1：In-order array是升序的
// 思路2：Recursion

/**
 * Definition for a binary tree node.
*/
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 中序遍历。将所有元素存储在一个数组vector中
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int> vec;
        inOrder(root, vec);
        // 判断是否是升序的
        for(int i = 1; i < vec.size(); i++)
            if(vec[i-1] >= vec[i])
                return false;
        return true;
    }

private:
    void inOrder(TreeNode* node, vector<int>& vec) {
        if(node == NULL)
            return;

        inOrder(node->left, vec);
        vec.push_back(node->val);
        inOrder(node->right, vec);
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
